package com.mgq.algorithm.twotree;

/**
 * 二叉树的最大距离问题
 * 树形DP的套路
 * 1.以某个节点x为头节点的子树,分析答案有哪些可能性,并且这种分析是以x的左子树,x的右子树和x整棵树的角度来考虑问题的
 * 2.根据第一步的可能性分析,列出所有需要的信息
 * 3.合并第二步的信息,对左树和右树提出同样的要求,并写出信息结构
 * 4.设计递归函数,递归函数是处理以x为头节点的情况下的答案
 *
 *
 */
public class MaxDistance {
    /**
     * 求node节点的最大举例
     * @param node
     * @return
     */
    public static int maxDistance(TreeNode node) {
        //不包含当前节点的情况:
        //最大距离是 来自左树的最大距离,或者右树的最大距离
        //包含当前节点时:
        //最大距离是来自 左树的高度+右树的高度+1
        //最终的值是取这3种情况的最大值
        return process(node).maxDistance;
    }

    public static Info process(TreeNode node) {
        //base case
        if (node == null) {
            return new Info(0, 0);
        }
        Info left = process(node.left);
        Info right = process(node.right);
        int maxDistance = Math.max(Math.max(left.maxDistance, right.maxDistance), (left.height + right.height + 1));
        //当前树的高度是取左树和右树的高度的最大值+1
        int height = Math.max(left.height , right.height) + 1;
        return new Info(maxDistance, height);
    }
    /**
     * 首先找可能性,构造信息结构
     */
    public static class Info{
        /**
         * 最大距离
         */
        private int maxDistance;
        /**
         * 高度
         */
        private int height;

        public Info(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }
}
